package com.lq.nine;

/**
 * @author lq
 * @date 2020-10-03 08:54
 */
public class T4findMedianSortedArrays {

    /**
     * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
     *
     * 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
     * @param args
     */
    public static void main(String[] args) {
        int[] nums1 = {1};
        int[] nums2 = {};
        double r = findMedianSortedArrays(nums1, nums2);
        System.out.println(r);
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int len = m + n;
        int left = -1, right = -1;
        int index1 = 0, index2 = 0;
        for (int i = 0; i <= len / 2; i++) {
            left = right;
            if (index1 < m && (index2 >= n || nums1[index1] < nums2[index2])) {
                right = nums1[index1++];
            } else {
                right = nums2[index2++];
            }
        }
        if ((len & 1) == 0) {
            return (left + right) / 2.0;
        }
        return right;
    }
}
